| Java集合（六）LinkedHashMap详解 | 您所在的位置：网站首页 › java 集合初始化大小 › Java集合（六）LinkedHashMap详解 |
Java集合（六）LinkedHashMap详解
|
本文目录 1 LinkedHashMap概述 2 LinkedHashMap 源码定义 2.1 类结构定义 2.2 成员变量定义 2.3 成员方法定义 2.4 基本元素 Entry 3 LinkedHashMap的方法 3.1 LinkedHashMap的构造方法 3.2 初始化方法init方法 3.3 LinkedHashMap的快速存取 3.3.1 LinkedHashMap 的存储实现 : put(key, vlaue) 3.3.2 LinkedHashMap 的扩容操作 : resize() 3.3.3 LinkedHashMap 的读取实现 ：get(Object key) 3.3.4 LinkedHashMap 存取小结 4 LinkedHashMap与LRU算法 4.1 put操作与标志位accessOrder 4.2 get操作与标志位accessOrder 4.3 LinkedListMap与LRU小结 5 使用LinkedHashMap实现LRU算法 5.1 使用LinkedHashMap实现LRU算法示例 5.2 LinkedHashMap 有序性原理分析 6 JDK1.8的修改 7 LinkedHashMap小结 1 LinkedHashMap概述HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。不过遗憾的是，HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。 HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。 特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。 LinkedHashMap与Map接口之间的继承关系如下图所示： 本质上，HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表的HashMap。 在LinkedHashMapMap中，所有put进来的Entry都保存在如下面第一个图所示的哈希表中，但由于它又额外定义了一个以head为头结点的双向链表(如下面第二个图所示)，因此对于每次put进来Entry，除了将其保存到哈希表中对应的位置上之外，还会将其插入到双向链表的尾部。 更直观地，下图很好地还原了LinkedHashMap的原貌：HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是，next用于维护HashMap各个桶中的Entry链，before、after用于维护LinkedHashMap的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。 其中，HashMap与LinkedHashMap的Entry结构示意图如下图所示： 特别地，由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，LinkedHashMap 也是 Map 的一个非同步的实现。此外，LinkedHashMap还可以用来实现LRU (Least recently used, 最近最少使用)算法，这个问题会在下文的特别谈到。 2 LinkedHashMap 源码定义 2.1 类结构定义LinkedHashMap继承于HashMap，其在JDK中的定义为： public class LinkedHashMap extends HashMap implements Map { ... } 2.2 成员变量定义与HashMap相比，LinkedHashMap增加了两个属性用于保证迭代顺序，分别是双向链表头结点header 和 标志位accessOrder (值为true时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代)。 /** * The head of the doubly linked list. */ private transient Entry header; // 双向链表的表头元素 /** * The iteration ordering method for this linked hash map: true * for access-order, false for insertion-order. * * @serial */ private final boolean accessOrder; //true表示按照访问顺序迭代，false时表示按照插入顺序 2.3 成员方法定义从下图我们可以看出，LinkedHashMap中并增加没有额外方法。也就是说，LinkedHashMap与HashMap在操作上大致相同，只是在实现细节上略有不同罢了。 LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了Entry。LinkedHashMap中的Entry增加了两个指针 before 和 after，它们分别用于维护双向链接列表。特别需要注意的是，next用于维护HashMap各个桶中Entry的连接顺序，before、after用于维护Entry插入的先后顺序的，源代码如下： private static class Entry extends HashMap.Entry { // These fields comprise the doubly linked list used for iteration. Entry before, after; Entry(int hash, K key, V value, HashMap.Entry next) { super(hash, key, value, next); } ... }形象地，HashMap与LinkedHashMap的Entry结构示意图如下图所示： LinkedHashMap 一共提供了五个构造函数，它们都是在HashMap的构造函数的基础上实现的，除了默认空参数构造方法，下面这个构造函数包含了大部分其他构造方法使用的参数，就不一一列举了。 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)该构造函数意在构造一个指定初始容量和指定负载因子的具有指定迭代顺序的LinkedHashMap，其源码如下： /** * Constructs an empty LinkedHashMap instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - true for * access-order, false for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) { super(initialCapacity, loadFactor); // 调用HashMap对应的构造函数 this.accessOrder = accessOrder; // 迭代顺序的默认值 }初始容量和负载因子是影响HashMap性能的两个重要参数。同样地，它们也是影响LinkedHashMap性能的两个重要参数。此外，LinkedHashMap 增加了双向链表头结点 header和标志位 accessOrder两个属性用于保证迭代顺序。 LinkedHashMap(Map |
【本文地址】